package com.company.ljh.hard;

/**
 * @description:
 * 790. 多米诺和托米诺平铺
 * 有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
 *
 *
 *
 * 给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
 *
 * 平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
 * @projectName:leet_code
 * @see:com.company.ljh.hard
 * @author:ljh
 * @createTime:2023/10/20 10:40
 * @version:1.0
 */
public class 多米诺和托米诺平铺 {
    public int numTilings(int n) {
        //建立dp方程，用0，1，2，3分别代表当前没有方块，当前上面一个方块，下面一个方块，两个方块的情况
        int dp[][]= new int[n][4];
        //初始化方程
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[0][2] = 0;
        //只有一个方块的情况下
        dp[0][3] = 1;
        //建立状态转换方程，
        //第一种情况，相当于第三种不填
        //dp[i][0] = dp[i-1][3]
        ////第二种情况，相当于第三种填一个个横方块，或者第一种填三角方块
        //dp[i][1] = dp[i-1][2]+dp[i-1][0];
        //第三种情况，与第二种类似，相当于第二种填一个横方块，或者第一种填倒三角
        //dp[i][2] = dp[i-1][1]+dp[i-1][0];
        //第四种，第一种填两个竖方块或者两个横方块，或者第二种填倒三角方块，或者第三种填三角方块，第四种填竖方块
        int baseNume = (int)Math.pow(10,9) + 7;
        //dp[i][3] = 2 * dp[i-1][0]+dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
        for(int i = 1;i<n;i++){
            dp[i][0] = dp[i-1][3];
            dp[i][1] = (dp[i-1][2]+dp[i-1][0]) %baseNume;
            dp[i][2] = (dp[i-1][1]+dp[i-1][0]) %baseNume;
            //防止超过int，加一次必须mod一次
            dp[i][3] = (((dp[i-1][0]+dp[i-1][1])% baseNume + dp[i-1][2])% baseNume + dp[i-1][3])%baseNume;
        }
        return dp[n-1][3] ;
    }
}
